package com.sx.sx1.lintcode.day717;

public class LC1063 {

    static class MyCalendarThree {

        SegmentNode root =null;
        public MyCalendarThree() {
            root= buildTree(0,100000);
        }

        public int book(int start, int end) {
            for (int i = start; i <end ; i++) {
                valPlus(root,i);
            }
            return root.total;
        }

        public SegmentNode buildTree(int start,int end){
            if(start == end){
                return new SegmentNode(start,end);
            }

            SegmentNode node = new SegmentNode(start,end);
            int  m = start+((end-start)>>1);
            node.left =  buildTree(start,m);
            node.right = buildTree(m+1,end);
            return node;
        }

        public void valPlus(SegmentNode node,int idx){
            if(node.start == node.end && node.start == idx){
                node.total+=1;
                return;
            }

            int m = node.start+((node.end-node.start)>>1);
            if(idx<=m) {
                valPlus(node.left,idx);
            }else{
                valPlus(node.right,idx);
            }

            node.total=Math.max(node.left.total,node.right.total);
        }
        static class SegmentNode{
            public int start,end,total;
            public SegmentNode left,right;
            public SegmentNode(int s,int e){
                start =s;
                end =e;
            }
        }
    }


    public static void main(String[] args) {
        MyCalendarThree obj = new MyCalendarThree();
        System.out.println(obj.book(10, 20));
        System.out.println(obj.book(50, 60));
        System.out.println(obj.book(10, 40));
        System.out.println(obj.book(5, 15));
        System.out.println(obj.book(5, 10));
        System.out.println(obj.book(25, 55));
    }

    static class MyCalendarThree1 {
        SegmentNode root; //线段树根节点

        public MyCalendarThree1() {
            root = build(0, 100000);
        }

        public int book(int start, int end) {
            for (int i = start; i < end; i++) {
                update(root, i, 1);
            }
            return root.max;
        }

        static class SegmentNode { //线段树节点定义
            int start, end, max;
            SegmentNode left, right;

            public SegmentNode(int s, int e) {
                start = s;
                end = e;
            }
        }

        //根据开始，结束标志，创建线段树
        public static SegmentNode build(int start, int end) {
            if (start > end) return null;
            if (start == end)
                return new SegmentNode(start, end);

            SegmentNode root = new SegmentNode(start, end);

            int mid = start + (end - start) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
            return root;
        }


        //更新线段树
        public static void update(SegmentNode root, int index, int val) {
            if (root.start == root.end && root.start == index) {
                root.max += val;
                return;
            }

            int mid = (root.start + root.end) / 2;
            if (index <= mid && index >= root.start) {
                update(root.left, index, val);
            }

            if (index > mid && index <= root.end) {
                update(root.right, index, val);
            }


            root.max = Math.max(root.left.max, root.right.max);
        }
    }

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有187条未读消息，请及时查看
1063 · 我的日历III
算法
困难
通过率
77%

题目
题解13
笔记
讨论12
排名
记录
描述
实现一个MyCalendarThree 来储存你的时间。一个新的事件 总是 可以被加入。

你的类会有一种方法：book(int start, int end)。 正式的说，这代表在一个半开区间 [start, end) 上进行预订，实数x 的范围即 start <= x < end。

当K个事件有一个非空交集的时候，一个K预订将会发生。（即，某一个时刻对于K个事件是共用的）

对于每一个对于方法 MyCalendar.book的调用，返回一个整数K，代表日历中存在K预订的最大的整数。

你的类将会这样被调用: MyCalendarThree cal = new MyCalendarThree(); MyCalendarThree.book(start, end)。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


每个测试用例将会调用 MyCalendarThree.book 至多400次 。
在调用MyCalendarThree.book(start, end)时， start 和 end是在[0, 10^9]内的整数。
样例
样例1
10......20
                    50.....60
10............40
   5..15
   5.10
          25...........55
输入:
MyCalendarThree()
book(10,20)
book(50,60)
book(10,40)
book(5,15)
book(5,10)
book(25,55)

输出: [1,1,2,3,3,3]
说明：
前两个可以被预订的事件是不相交的，所以说最大的K预订是1预订。
第三个事件[10,  40)和第一个事件相交，最大的K预订是2预订。
剩下的事件导致最大的K预订只是3预订。
注意到最后一个事件在本地导致2预订，但是答案依然是3预订
因为比如， [10, 20), [10, 40), and [5, 15)依然是三重预订。
样例2

输入:
MyCalendarThree()
book(1,2)
book(1,2)
book(2,3)

输出: [1,2,2]
标签
企业
Google
相关题目

1064
我的日程表 II
中等

1065
我的日程安排表 I
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
已开启智能提示
发起考试
45 分 00 秒
12345678910111213141516
class MyCalendarThree {

    public MyCalendarThree() {

    }

    public int book(int start, int end) {

    }
}

控制台
历史提交

 */
